package hot100;


/*
 * Author：江松
 * Date：2023/4/22 10:19
 *
 括号生成：
 DFS
 */

import java.util.LinkedList;
import java.util.List;

public class Main22 {
    private int n;
    private List<String>res=new LinkedList<>();
    public void dfs(int sc,String now){
        if(sc<0)return;
        if(now.length()>2*n)return;
        // System.out.println(now);
        if(now.length()==2*n&&sc==0){
            res.add(now);
            return;
        }
        dfs(sc+1,now+String.valueOf('('));
        dfs(sc-1,now+String.valueOf(')'));
    }

    public List<String> generateParenthesis(int n) {
        this.n=n;
        dfs(0,"");
        return res;
    }
}
